UVa/10249 - The grand dinner/10249.3.cpp

   1 /*
   2   Problem: 10249 - The grand dinner
   3   Andrés Mejía-Posada (andmej@gmail.com)
   4
   5   Accepted
   6   Greedy
   7 */
   8 using namespace std;
   9 #include <algorithm>
  10 #include <iostream>
  11 #include <iterator>
  12 #include <sstream>
  13 #include <fstream>
  14 #include <cassert>
  15 #include <climits>
  16 #include <cstdlib>
  17 #include <cstring>
  18 #include <string>
  19 #include <cstdio>
  20 #include <vector>
  21 #include <cmath>
  22 #include <queue>
  23 #include <deque>
  24 #include <stack>
  25 #include <list>
  26 #include <map>
  27 #include <set>
  28
  29 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  30 #define D(x) cout << #x " is " << x << endl
  31 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  32
  33 const int MAXN = 135;
  34 vector<int> g[MAXN];
  35
  36 int main(){
  37   int nteams, ntables;
  38   while (scanf("%d %d", &nteams, &ntables)==2 && nteams && ntables){
  39     int people = 0, spots = 0;
  40     for (int i=0; i<nteams; ++i) g[i].clear();
  41     vector<pair<int, int> > teams(nteams), tables(ntables);
  42     for (int i=0, c; i<nteams; ++i){
  43       scanf("%d", &c);
  44       teams[i] = make_pair(c, i);
  45       people += c;
  46     }
  47     for (int i=0, c; i<ntables; ++i){
  48       scanf("%d", &c);
  49       tables[i] = make_pair(c, i);
  50       spots += c;
  51     }
  52     if (people > spots){ printf("0\n"); continue; }
  53
  54     int f = 0;
  55     sort(teams.begin(), teams.end(), greater<pair<int, int> >());
  56     sort(tables.begin(), tables.end(), greater<pair<int, int> >());
  57     for (int i=0; i<teams.size(); ++i){
  58       for (int j=0; j<tables.size() && teams[i].first > 0; ++j){
  59         if (tables[j].first > 0){
  60           teams[i].first--;
  61           tables[j].first--;
  62           g[teams[i].second].push_back(tables[j].second);
  63           ++f;
  64         }
  65       }
  66     }
  67
  68     if (f < people){
  69       printf("0\n");
  70     }else{
  71       printf("1\n");
  72       for (int i=0; i<nteams; ++i){
  73         bool first = true;
  74         foreach(v, g[i]){
  75           int j = *v;
  76           if (!first) printf(" ");
  77           first = false;
  78           printf("%d", j+1);
  79         }
  80         printf("\n");
  81       }
  82     }
  83   }
  84   return 0;
  85 }